Lecture on Approximation Algorithms at the Parisian Computer Science Master<br />by Nicolas Schabanel<br />[ Lecture 4 Part B/C ]<br /><br />Lecture 4: Wed Nov 7, 2012 - 12:45-15:45<br /> Hardness of approximation: The PCP theorem by GAP amplification<br /> 1) A little bit of history<br /> 2) Gap problems and Hardness of approximation<br /> 3) The CSP: Graph Constraints Satisfaction Problem<br /> 4) Overview of the Gap amplication process 2.a) definition<br /> 5) A key tool: Expander graphs I<br /> 6) Step 1: Degree uniformization<br /> 7) Step 2: Expanderization<br /> 8) Expander graphs II: spectral theory and random walks<br /> 9) Step 3: Gap amplification<br /> 10) Step 4 (last): Alphabet reduction<br /> 11) Gap-preserving reductions<br /><br />Exercises session 4:<br /> 1) Gap-preserving reductions for Vertex-Cover and Steiner Tree<br /> 2) Random walks on expanders
